import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

/**
 * Created by JiaJia on 2019/5/23 0023.
 * 按之字形打印二叉树
 * 与逐行打印二叉树相比，偶数行需要反转打印
 * 用到了Collections的reverse方法
 */
public class Code60 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrayList=new ArrayList<>();
        LinkedList<TreeNode> queue=new LinkedList<>();
        if (pRoot==null)
            return arrayList;
        queue.add(pRoot);
        boolean reverse=false;
        while (!queue.isEmpty()){
            ArrayList<Integer> list=new ArrayList<>();
            int count=queue.size();
            while (count-->0){
                TreeNode node=queue.poll();
                if (node==null)
                    continue;
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            if (reverse){
                Collections.reverse(list);
            }
            reverse= !reverse;
            if (list.size()!=0)
                arrayList.add(list);
        }
        return arrayList;
    }
}